package leetcode

import kotlinetc.println


fun main(args: Array<String>) {

}

fun wordSubsets(A: Array<String>, B: Array<String>): List<String> {

    val res = arrayListOf<String>()

    val table = Array(26, { 0 })
    var count = 0

    //把 B压缩成一个字母的记录表，避免每次对B中每个字符串检测 m*n 缩短成 m
    B.forEach {
        val tmpTable = Array(26) { 0 }
        it.forEach {
            val i = it.toInt() - 'a'.toInt()
            if (table[i] == 0) count++  //new letter
            tmpTable[i]++
            table[i] = Math.max(tmpTable[i], table[i])
        }
    }


    val b = ""


    A.forEach { a ->
        if (isSubsets(table, count, a)) {
            res.add(a)
        }
    }

    return res

}


fun isSubsets(table: Array<Int>, count: Int, b: String): Boolean {
    if (count > b.length) return false
//    val table = Array(26) { 0 }
    val bTable = Array(26) { 0 }
    var bCount = 0

    b.forEach {
        val i = it.toInt() - 'a'.toInt()
        if (table[i] != 0) {
            bTable[i]++
            if (bTable[i] == table[i])//有一个字母完成匹配
                bCount++
        }

    }

    return count == bCount
}